package bit;

import java.util.ArrayList;
import java.util.List;


/**
 * https://leetcode-cn.com/problems/subsets/solution/78-zi-ji-yong-shu-lai-mo-ni-hui-su-suan-y5h28/
 * 设计回溯都可以使用树来分析
 */
class 子集_78_回溯法 {
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<>());
        return res;
    }


    private void backtrack(int[] nums, int startIdx, List<Integer> item) {
        // 需要保存全部的子集 因此非叶子节点也需要保存
        res.add(new ArrayList(item));
        if (startIdx >= nums.length) {
            return;
        }
        // 需要从之前的状态向后搜索 因此需要保存之前的状态  startIdx
        for(int i = startIdx; i< nums.length; i++) {
            item.add(nums[i]);
            backtrack(nums, i + 1, item);
            item.remove(item.size() - 1);
        }
    }
}


public class 子集_78 {

    /**
     * 位运算法
     */
    public List<List<Integer>> subsets_bit(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0; i < (1<<nums.length) ; i++) {
            List<Integer> subSetTmp = new ArrayList<>();
            // 1<< 0  == 1
            for(int j = 0; j < nums.length; j ++) {
                if( ((1<<j) & i) != 0 ) {
                    subSetTmp.add(nums[i]);
                }
            }
            res.add(subSetTmp);
        }
        return res;
    }


    /**
     * 分治法  对于每一位 可以选也可以不选  递归遍历即可
     */

    List<List<Integer>> res = new ArrayList<>();
    List<Integer> tmp = new ArrayList<>();
    public List<List<Integer>> subsets_divide(int[] nums) {
        divide(nums, 0);
        return res;
    }
    /**
     * 递归到第n个数组
     *
     * 子集枚举模板
     */
    public void divide(int[] nums, int n) {
        if(n > nums.length - 1){
            res.add(new ArrayList<>(tmp));
            return;
        }
        // 加上当前元素后递归
        tmp.add(nums[n]);
        divide(nums, n+1);
        // 每次退出后删掉最后一个
        // 类似与出入栈， 到本函数栈的时候回原了
        tmp.remove(tmp.size() - 1);
        // 不要当前元素后递归
        divide(nums, n+ 1);


    }


    public static void main(String[] args) {
        子集_78 a = new 子集_78();
        List<List<Integer>> lists = a.subsets_divide(new int[]{1, 2, 3});
        System.out.println(lists);
    }

}
